#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

/**
 * @brief 使用hash表来求解最长连续序列
 * hash表是用来记录到目前这个key的最长连续序列长度
 * 若这个数不在hash表中，则可以根据这个数左右所已经达到的最长序列来更新
 */
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int max_len = 0;
        map<int,int> dict;
        for(auto num : nums){
            // 当前数不在hash表中
            if(dict.find(num) == dict.end()){
                int left = 0,right = 0;
                if(dict.find(num-1)!=dict.end()){
                    left = dict[num-1];
                }
                if(dict.find(num+1)!=dict.end()){
                    right = dict[num+1];
                }
                int cur_len = left + right + 1;
                max_len = max(max_len,cur_len);

                dict[num] = cur_len;
                dict[num-left] = cur_len;
                dict[num+right] = cur_len;
            }
        }
        return max_len;
    }
};

int main()
{
    Solution solution;
    vector<int> input = {100,4,1,3,2};
    cout<<solution.longestConsecutive(input)<<endl;
    return 0;
}